{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Number of the Smallest Unoccupied Chair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #ordered-set #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #有序集合 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestChair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小未被占据椅子的编号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个朋友在举办一个派对，这些朋友从 <code>0</code> 到 <code>n - 1</code> 编号。派对里有 <strong>无数</strong> 张椅子，编号为 <code>0</code> 到 <code>infinity</code> 。当一个朋友到达派对时，他会占据 <strong>编号最小</strong> 且未被占据的椅子。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，当一个朋友到达时，如果椅子 <code>0</code> ，<code>1</code> 和 <code>5</code> 被占据了，那么他会占据 <code>2</code> 号椅子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>times</code> ，其中 <code>times[i] = [arrival<sub>i</sub>, leaving<sub>i</sub>]</code> 表示第 <code>i</code> 个朋友到达和离开的时刻，同时给你一个整数 <code>targetFriend</code> 。所有到达时间 <strong>互不相同</strong> 。</p>\n",
    "\n",
    "<p>请你返回编号为 <code>targetFriend</code> 的朋友占据的 <strong>椅子编号</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>times = [[1,4],[2,3],[4,6]], targetFriend = 1\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>\n",
    "- 朋友 0 时刻 1 到达，占据椅子 0 。\n",
    "- 朋友 1 时刻 2 到达，占据椅子 1 。\n",
    "- 朋友 1 时刻 3 离开，椅子 1 变成未占据。\n",
    "- 朋友 0 时刻 4 离开，椅子 0 变成未占据。\n",
    "- 朋友 2 时刻 4 到达，占据椅子 0 。\n",
    "朋友 1 占据椅子 1 ，所以返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>times = [[3,10],[1,5],[2,6]], targetFriend = 0\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "- 朋友 1 时刻 1 到达，占据椅子 0 。\n",
    "- 朋友 2 时刻 2 到达，占据椅子 1 。\n",
    "- 朋友 0 时刻 3 到达，占据椅子 2 。\n",
    "- 朋友 1 时刻 5 离开，椅子 0 变成未占据。\n",
    "- 朋友 2 时刻 6 离开，椅子 1 变成未占据。\n",
    "- 朋友 0 时刻 10 离开，椅子 2 变成未占据。\n",
    "朋友 0 占据椅子 2 ，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == times.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>times[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= arrival<sub>i</sub> &lt; leaving<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= targetFriend &lt;= n - 1</code></li>\n",
    "\t<li>每个 <code>arrival<sub>i</sub></code> 时刻 <strong>互不相同</strong> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-number-of-the-smallest-unoccupied-chair](https://leetcode.cn/problems/the-number-of-the-smallest-unoccupied-chair/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-number-of-the-smallest-unoccupied-chair](https://leetcode.cn/problems/the-number-of-the-smallest-unoccupied-chair/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4],[2,3],[4,6]]\\n1', '[[3,10],[1,5],[2,6]]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        chair = [0] * n\n",
    "        order = sorted(range(n), key=lambda i:times[i])\n",
    "        for i in order:\n",
    "            arrive, leave = times[i]\n",
    "            for j, chair_leave in enumerate(chair):\n",
    "                if arrive >= chair_leave:\n",
    "                    if i == targetFriend:\n",
    "                        return j\n",
    "                    chair[j] = leave\n",
    "                    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        start = times[targetFriend][0]\n",
    "        visit = []\n",
    "        seat = list(range(len(times)))\n",
    "        tmp = times[targetFriend][0]\n",
    "        for reach, arrival in sorted(times, key=lambda x: x[0]):\n",
    "            while visit and visit[0][0] <= reach:\n",
    "                heapq.heappush(seat, heapq.heappop(visit)[1])\n",
    "            idx = heapq.heappop(seat)\n",
    "            heapq.heappush(visit, (arrival, idx))\n",
    "            if start == reach:\n",
    "                return idx\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        idx = list(range(n))\n",
    "        q = []\n",
    "        now = 0\n",
    "        ready = []\n",
    "        idx.sort(key=lambda i:times[i][0])\n",
    "        for i in idx:\n",
    "            start, end = times[i]\n",
    "            while q and q[0][0] <= start:\n",
    "                _, target = heappop(q)\n",
    "                heappush(ready, target)\n",
    "            if ready:\n",
    "                target = heappop(ready)\n",
    "            else:\n",
    "                target = now\n",
    "                now += 1\n",
    "            heappush(q, (end, target))\n",
    "            if i == targetFriend:\n",
    "                return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        heap = [[0, 0]]\n",
    "        n = len(times)\n",
    "        index = sorted(range(n), key = lambda x: times[x][0])\n",
    "        empty = list(range(1, n))\n",
    "        i = 0\n",
    "        while index[i] != targetFriend:\n",
    "            if heap[0][0] <= times[index[i]][0]:\n",
    "                while heap and heap[0][0] <= times[index[i]][0]:\n",
    "                    _, idx = heapq.heappop(heap)\n",
    "                    heapq.heappush(empty, idx)\n",
    "            heapq.heappush(heap, [times[index[i]][1], empty[0]])\n",
    "            heapq.heappop(empty)\n",
    "            i += 1\n",
    "        while heap and heap[0][0] <= times[index[i]][0]:\n",
    "            _, idx = heapq.heappop(heap)\n",
    "            heapq.heappush(empty, idx)\n",
    "        return empty[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "    '''\n",
    "    维护当前最小椅子编号\n",
    "    维护当前最小的结束时间\n",
    "    按照先来后到遍历\n",
    "    '''\n",
    "    targetstart = times[targetFriend][0]\n",
    "    times.sort()\n",
    "    n = len(times)\n",
    "    mnchair = list(range(n))  # 空闲椅子编号\n",
    "    endtime = []  # 结束时间\n",
    "    for s, e in times:\n",
    "      '''\n",
    "      用开始时间去pop之前的结束时间,\n",
    "      并把椅子释放，加入到空闲椅子中\n",
    "      '''\n",
    "      while endtime and s >= endtime[0][0]:\n",
    "        _ , chair = heappop(endtime)\n",
    "        heappush(mnchair, chair)\n",
    "      '''\n",
    "      取出最小编号椅子c，并存入结束时间\n",
    "      '''\n",
    "      c = heappop(mnchair)\n",
    "      if s == targetstart:\n",
    "        return c\n",
    "      heappush(endtime, (e, c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        visit = [0] * n\n",
    "        tmp = sorted(list((x, y, i) for i, (x, y) in enumerate(times)), key=lambda x: x[0])\n",
    "        for x, y, z in tmp:\n",
    "            for j in range(n):\n",
    "                if visit[j] == 0:\n",
    "                    visit[j] = -y\n",
    "                elif visit[j] + x >= 0:\n",
    "                    visit[j] = -y\n",
    "                else:\n",
    "                    continue\n",
    "                if z == targetFriend:\n",
    "                    return j\n",
    "                break      \n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        visit = [0] * n\n",
    "        tmp = sorted(list((x, y, i) for i, (x, y) in enumerate(times)), key=lambda x: x[0])\n",
    "        for x, y, z in tmp:\n",
    "            for j in range(n):\n",
    "                if visit[j] + x >= 0:\n",
    "                    visit[j] = -y\n",
    "                    if z == targetFriend:\n",
    "                        return j\n",
    "                    break    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        chair=[0]*len(times)\n",
    "        min_num=0\n",
    "\n",
    "        times2=sorted(times, key=lambda x: (x[0], x[1]))\n",
    "\n",
    "        tX=times[targetFriend][0]\n",
    "\n",
    "        for i in range(len(times2)):    \n",
    "            tt=times2[i]\n",
    "            #chair[min_num]=tt[1]\n",
    "            for cc in range(len(chair)):\n",
    "                if chair[cc]<=tt[0]:\n",
    "                    chair[cc]=tt[1]\n",
    "                    #print(chair)\n",
    "                    #print(cc)\n",
    "                    min_num=cc\n",
    "                    break\n",
    "            if tt[0]==tX:\n",
    "                break      \n",
    "\n",
    "        return min_num    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        visit = [0] * n\n",
    "        tmp = sorted(list((x, y, i) for i, (x, y) in enumerate(times)), key=lambda x: x[0])\n",
    "        for x, y, z in tmp:\n",
    "            for j in range(n):\n",
    "                if visit[j] == 0:\n",
    "                    visit[j] = -y\n",
    "                elif visit[j] + x >= 0:\n",
    "                    visit[j] = -y\n",
    "                else:\n",
    "                    continue\n",
    "                if z == targetFriend:\n",
    "                    return j\n",
    "                break      \n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        visit = [0] * n\n",
    "        tmp = times[targetFriend][0]\n",
    "        for x, y in sorted(times, key=lambda x: x[0]):\n",
    "            for i in range(n):\n",
    "                if visit[i] + x >= 0:\n",
    "                    visit[i] = -y\n",
    "                    if x == tmp:\n",
    "                        return i\n",
    "                    break    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        chair = [*range(n)] # 储存空椅子\n",
    "        leaves = []  # 储存（离开时间，椅子下标）\n",
    "        for i in sorted(range(n), key=lambda i:times[i]):\n",
    "            enter, leave = times[i]\n",
    "            while leaves and enter >= leaves[0][0]:\n",
    "                _, new = heappop(leaves)\n",
    "                heappush(chair, new)\n",
    "            seat = heappop(chair)\n",
    "            if i == targetFriend:\n",
    "                return seat\n",
    "            heappush(leaves, (leave, seat))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        arrive_t = times[targetFriend][0]\n",
    "        times = sorted(times,key = lambda x:x[0])\n",
    "        seat = []\n",
    "        for i in times:\n",
    "            flg = False\n",
    "            for j in range(len(seat)):\n",
    "                if seat[j]<=i[0]:\n",
    "                    if i[0]==arrive_t:\n",
    "                        return j\n",
    "                    flg = True\n",
    "                    seat[j] = i[1]\n",
    "                    break\n",
    "            if not flg:\n",
    "                if i[0]==arrive_t:\n",
    "                    return len(seat)\n",
    "                seat.append(i[1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        avail = []\n",
    "        o = -1\n",
    "        sitting = []\n",
    "        for i in sorted(range(len(times)),key=lambda i: times[i][0]):\n",
    "            arv, lv = times[i]\n",
    "            while sitting and sitting[0][0]<=arv:\n",
    "                _, chair = heapq.heappop(sitting)\n",
    "                heapq.heappush(avail, chair)\n",
    "            \n",
    "            chair = heapq.heappop(avail) if avail else (o:=o+1)\n",
    "            heapq.heappush(sitting, [lv,chair])\n",
    "\n",
    "            if i == targetFriend:\n",
    "                return chair\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times, targetFriend):\n",
    "        arrive_time, max_chair_id = times[targetFriend][0], 0\n",
    "        que = []\n",
    "        que_chair = []\n",
    "        times = sorted(times)\n",
    "\n",
    "        for arrival, leaving in times:\n",
    "            if arrival <= arrive_time:\n",
    "                while que and que[0][0] <= arrival:\n",
    "                    cur_leave_time, cur_leave_chair = heappop(que)\n",
    "                    heappush(que_chair, cur_leave_chair)\n",
    "\n",
    "                ans = 0\n",
    "                if que_chair:\n",
    "                    ans = heappop(que_chair)\n",
    "                    heappush(que, (leaving, ans))\n",
    "                else:\n",
    "                    ans = max_chair_id\n",
    "                    heappush(que, (leaving, max_chair_id))\n",
    "                    max_chair_id += 1\n",
    "\n",
    "                if arrive_time == arrival:\n",
    "                    return ans\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        chair=[0]*len(times)\n",
    "        min_num=0\n",
    "\n",
    "        #times2=sorted(times, key=lambda x: (x[0], x[1]))\n",
    "        times2=sorted(times,key=lambda x: (x[0],x[1]))\n",
    "\n",
    "        tX=times[targetFriend][0]\n",
    "\n",
    "        for i in range(len(times2)):    \n",
    "            tt=times2[i]\n",
    "            #chair[min_num]=tt[1]\n",
    "            for cc in range(len(chair)):\n",
    "                if chair[cc]<=tt[0]:\n",
    "                    chair[cc]=tt[1]\n",
    "                    #print(chair)\n",
    "                    #print(cc)\n",
    "                    min_num=cc\n",
    "                    break\n",
    "            if tt[0]==tX:\n",
    "                break      \n",
    "\n",
    "        return min_num    \n",
    "\n",
    "        #test=sorted(test1,key=lambda:x(x[0],x[1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "    '''\n",
    "    维护当前空闲最小椅子编号\n",
    "    维护之前的那些人的最小的结束时间\n",
    "    按照先来后到顺序遍历\n",
    "    '''\n",
    "    targetstart = times[targetFriend][0]\n",
    "    times.sort()\n",
    "    n = len(times)\n",
    "    mnchair = list(range(n))  # 空闲椅子编号\n",
    "    endtime = []  # 结束时间\n",
    "    for s, e in times:\n",
    "      '''\n",
    "      用开始时间去pop之前的结束时间,\n",
    "      并把占用的椅子释放，加入到空闲椅子中\n",
    "      '''\n",
    "      while endtime and s >= endtime[0][0]:\n",
    "        _ , chair = heappop(endtime)\n",
    "        heappush(mnchair, chair)\n",
    "      '''\n",
    "      取出最小编号椅子c，并存入结束时间和椅子编号c\n",
    "      '''\n",
    "      c = heappop(mnchair)\n",
    "      if s == targetstart:\n",
    "        return c\n",
    "      heappush(endtime, (e, c))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        arri = []\n",
    "        for i, x in enumerate(times):\n",
    "            heapq.heappush(arri, (x[0], x[1], i))\n",
    "\n",
    "        leav = []\n",
    "        free_c = []\n",
    "        chair_no = 0\n",
    "        while arri:\n",
    "            st, ed, idx = heapq.heappop(arri)\n",
    "            while leav and st>=leav[0][0]:\n",
    "                _, c_idx = heapq.heappop(leav)\n",
    "                heapq.heappush(free_c, c_idx)\n",
    "            \n",
    "            cur_c = -1\n",
    "            if free_c:\n",
    "                cur_c = heapq.heappop(free_c)\n",
    "            else:\n",
    "                cur_c = chair_no\n",
    "                chair_no += 1\n",
    "            if idx==targetFriend:\n",
    "                return cur_c\n",
    "            \n",
    "            heapq.heappush(leav, (ed, cur_c))\n",
    "            \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        friends = []\n",
    "        for time in times:\n",
    "            if time[0] <= times[targetFriend][0]:\n",
    "                friends.append(time)\n",
    "        friends = sorted(friends, key=lambda x: x[0])\n",
    "\n",
    "        usable = list(range(len(friends)))\n",
    "        heapq.heapify(usable)\n",
    "        using = []\n",
    "\n",
    "        chair = len(usable) - 1\n",
    "        for arrival, leave in friends:\n",
    "            while using and using[0][0] <= arrival:\n",
    "                _, free_chair = heapq.heappop(using)\n",
    "                heapq.heappush(usable, free_chair)\n",
    "\n",
    "            chair = heapq.heappop(usable)\n",
    "            heapq.heappush(using, (leave, chair))\n",
    "        return chair\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        m = (i for i in range(n))\n",
    "        seats = []\n",
    "        hp = []\n",
    "        times = [(x[0], x[1], i) for i, x in enumerate(times)]\n",
    "        heapq.heapify(times)\n",
    "        heapq.heapify(hp)\n",
    "        heapq.heapify(seats)\n",
    "        while times:\n",
    "            arrive_time, leave_time, i = heapq.heappop(times)\n",
    "            if not hp:\n",
    "                if not seats:\n",
    "                    heapq.heappush(seats, next(m))\n",
    "                heapq.heappush(hp, (leave_time, heapq.heappop(seats), i))\n",
    "            else:\n",
    "                while hp and hp[0][0] <= arrive_time:\n",
    "                    time, seat, friend = heapq.heappop(hp)\n",
    "                    if friend == targetFriend:\n",
    "                        return seat\n",
    "                    heapq.heappush(seats, seat)\n",
    "                if not seats:\n",
    "                    heapq.heappush(seats, next(m))\n",
    "                heapq.heappush(hp, (leave_time, heapq.heappop(seats), i))\n",
    "        while hp:\n",
    "            time, seat, friend = heapq.heappop(hp)\n",
    "            if friend == targetFriend:\n",
    "                return seat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        seats = [i for i in range(n)]\n",
    "        hp = []\n",
    "        times = [(x[0], x[1], i) for i, x in enumerate(times)]\n",
    "        heapq.heapify(times)\n",
    "        heapq.heapify(hp)\n",
    "        heapq.heapify(seats)\n",
    "        while times:\n",
    "            arrive_time, leave_time, i = heapq.heappop(times)\n",
    "            if not hp:\n",
    "                heapq.heappush(hp, (leave_time, heapq.heappop(seats), i))\n",
    "            else:\n",
    "                while hp and hp[0][0] <= arrive_time:\n",
    "                    time, seat, friend = heapq.heappop(hp)\n",
    "                    if friend == targetFriend:\n",
    "                        return seat\n",
    "                    heapq.heappush(seats, seat)\n",
    "                heapq.heappush(hp, (leave_time, heapq.heappop(seats), i))\n",
    "        while hp:\n",
    "            time, seat, friend = heapq.heappop(hp)\n",
    "            if friend == targetFriend:\n",
    "                return seat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], target: int) -> int:\n",
    "        usable, using = [], []\n",
    "        chair = -1\n",
    "        events = sorted((*x, i) for i, x in enumerate(times))\n",
    "\n",
    "        for s, e, i in events:\n",
    "            while using and using[0][0] <= s:\n",
    "                _, free = heapq.heappop(using)\n",
    "                heapq.heappush(usable, free)\n",
    "\n",
    "            if not usable:\n",
    "                best = chair = chair + 1\n",
    "            else:\n",
    "                best = heapq.heappop(usable)\n",
    "            if i == target:\n",
    "                return best\n",
    "            heapq.heappush(using, (e, best))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        taken = [] # (leaving, id)\n",
    "        ids = list(range(len(times)))\n",
    "        times = sorted([(l, r, i) for i, (l, r) in enumerate(times)])\n",
    "        for l, r, i in times:\n",
    "            while taken and taken[0][0] <= l:\n",
    "                heappush(ids, heappop(taken)[1])\n",
    "            if i == targetFriend:\n",
    "                return heappop(ids)\n",
    "            heappush(taken, [r, heappop(ids)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], target: int) -> int:\n",
    "\n",
    "        usable, using = [], []\n",
    "        chair = -1\n",
    "        events = sorted((*x, i) for i, x in enumerate(times))\n",
    "\n",
    "        for s, e, i in events:\n",
    "            while using and using[0][0] <= s:\n",
    "                _, free = heapq.heappop(using)\n",
    "                heapq.heappush(usable, free)\n",
    "\n",
    "            if not usable:\n",
    "                best = chair = chair + 1\n",
    "            else:\n",
    "                best = heapq.heappop(usable)\n",
    "            if i == target:\n",
    "                return best\n",
    "            heapq.heappush(using, (e, best))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        avails = []\n",
    "        used = []\n",
    "        mx = 0\n",
    "        for arrival, leaving, person in sorted((arrival, leaving, i) for i, (arrival, leaving) in enumerate(times)):\n",
    "            while used and used[0][0] <= arrival:\n",
    "                heapq.heappush(avails, heapq.heappop(used)[1])\n",
    "            seat = mx \n",
    "            if avails:\n",
    "                seat = heapq.heappop(avails)\n",
    "            else:\n",
    "                mx += 1\n",
    "            if person == targetFriend:\n",
    "                return seat \n",
    "            heapq.heappush(used, (leaving, seat))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        avails = []\n",
    "        used = []\n",
    "        seat = mx = 0\n",
    "        for arrival, leaving, person in sorted((arrival, leaving, i) for i, (arrival, leaving) in enumerate(times)):\n",
    "            while used and used[0][0] <= arrival:\n",
    "                heapq.heappush(avails, heapq.heappop(used)[1])           \n",
    "            if avails:\n",
    "                seat = heapq.heappop(avails)\n",
    "            else:\n",
    "                seat = mx \n",
    "                mx += 1\n",
    "            if person == targetFriend:\n",
    "                break\n",
    "            heapq.heappush(used, (leaving, seat))\n",
    "            \n",
    "        return seat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []\n",
    "        leaving = []\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))\n",
    "        seats = {}\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                return seat\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []   # 到达操作的时刻和对应的人\n",
    "        leaving = []   # 离开操作的时刻和对应的人\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        # 将到达与离开操作按照时间升序排序以方便模拟\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))   # 未被占据的椅子\n",
    "        seats = {}   # 每个人占据的椅子\n",
    "        # 双指针模拟\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            # 处理到达时间与之前的离开操作\n",
    "            # 将释放的椅子加入未被占据椅子中\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            # 处理到达操作\n",
    "            # 占据当前编号最小且未被占据的椅子\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                # 如果当前人为目标，则返回对应的椅子\n",
    "                return seat\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        times = [(a, b, i) for i, (a, b) in enumerate(times)]\n",
    "        times.sort()\n",
    "        from sortedcontainers import SortedList\n",
    "        m = SortedList([])\n",
    "        q = SortedList([i for i in range(n)])\n",
    "        \n",
    "        for a, b, i in times:\n",
    "            while m and m[0][0] <= a:\n",
    "                q.add(m[0][1])\n",
    "                m.remove(m[0])    \n",
    "            f = q[0]\n",
    "            m.add((b, f))\n",
    "            q.remove(f)\n",
    "            \n",
    "            if i == targetFriend:\n",
    "                return f\n",
    "        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        times = [[times[i][0], times[i][1], i] for i in range(n)]\n",
    "        times.sort()\n",
    "        for i in range(n):\n",
    "            if(times[i][2] == targetFriend):\n",
    "                targetFriend = i \n",
    "                break\n",
    "        number = 0\n",
    "        heap1 = [] #被占\n",
    "        heap2 = [] #释放\n",
    "        for i in range(n):\n",
    "            a, l, _ = times[i]\n",
    "            while(heap1 and heap1[0][0] <= a):\n",
    "                _, num = heapq.heappop(heap1)\n",
    "                heapq.heappush(heap2, num)\n",
    "            if(len(heap2) == 0):\n",
    "                tmp = number\n",
    "                number += 1\n",
    "            else:\n",
    "                tmp = heapq.heappop(heap2)\n",
    "            heapq.heappush(heap1, [l,tmp])\n",
    "            if(i == targetFriend):\n",
    "                return tmp \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        # 椅子编号堆和椅子释放时间堆\n",
    "        chairs, releases = [], []\n",
    "        \n",
    "        # 初始化椅子编号堆\n",
    "        for i in range(len(times)):\n",
    "            heapq.heappush(chairs, i)\n",
    "            \n",
    "        # 添加原始索引到times，并按到达时间排序\n",
    "        times = [[arrival, leaving, idx] for idx, (arrival, leaving) in enumerate(times)]\n",
    "        times.sort(key=lambda x: x[0])\n",
    "        \n",
    "        for arrival, leaving, idx in times:\n",
    "            # 检查是否有椅子被释放\n",
    "            while releases and releases[0][0] <= arrival:\n",
    "                _, chair = heapq.heappop(releases)\n",
    "                heapq.heappush(chairs, chair)\n",
    "                \n",
    "            # 给到达的朋友分配椅子\n",
    "            chair = heapq.heappop(chairs)\n",
    "            \n",
    "            if idx == targetFriend:\n",
    "                return chair\n",
    "            \n",
    "            # 将椅子的释放时间添加到releases堆中\n",
    "            heapq.heappush(releases, (leaving, chair))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "#         occupied = [0] * len(times)\n",
    "#         targetFriendarrive = times[targetFriend][0]\n",
    "#         times = sorted(times, key = lambda x:x[0])\n",
    "#         for i in range(len(times)):\n",
    "#             for j in range(len(times)):\n",
    "#                 if occupied[j] <= times[i][0]:\n",
    "#                     occupied[j] = times[i][1]\n",
    "#                     if times[i][0] == targetFriendarrive:\n",
    "#                         return j\n",
    "#                     break\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []   # 到达操作的时刻和对应的人\n",
    "        leaving = []   # 离开操作的时刻和对应的人\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        # 将到达与离开操作按照时间升序排序以方便模拟\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))   # 未被占据的椅子\n",
    "        seats = {}   # 每个人占据的椅子\n",
    "        # 双指针模拟\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            # 处理到达时间与之前的离开操作\n",
    "            # 将释放的椅子加入未被占据椅子中\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            # 处理到达操作\n",
    "            # 占据当前编号最小且未被占据的椅子\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                # 如果当前人为目标，则返回对应的椅子\n",
    "                return seat\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        times = [[times[i][0], times[i][1], i] for i in range(n)]\n",
    "        times.sort()\n",
    "        for i in range(n):\n",
    "            if(times[i][2] == targetFriend):\n",
    "                targetFriend = i \n",
    "                break\n",
    "        number = 0\n",
    "        heap1 = [] #被占\n",
    "        heap2 = [] #释放\n",
    "        for i in range(n):\n",
    "            a, l, _ = times[i]\n",
    "            while(heap1 and heap1[0][0] <= a):\n",
    "                _, num = heapq.heappop(heap1)\n",
    "                heapq.heappush(heap2, num)\n",
    "            if(len(heap2) == 0):\n",
    "                tmp = number\n",
    "                number += 1\n",
    "            else:\n",
    "                tmp = heapq.heappop(heap2)\n",
    "            heapq.heappush(heap1, [l,tmp])\n",
    "            if(i == targetFriend):\n",
    "                return tmp \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []   # 到达操作的时刻和对应的人\n",
    "        leaving = []   # 离开操作的时刻和对应的人\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        # 将到达与离开操作按照时间升序排序以方便模拟\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))   # 未被占据的椅子\n",
    "        seats = {}   # 每个人占据的椅子\n",
    "        # 双指针模拟\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            # 处理到达时间与之前的离开操作\n",
    "            # 将释放的椅子加入未被占据椅子中\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            # 处理到达操作\n",
    "            # 占据当前编号最小且未被占据的椅子\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                # 如果当前人为目标，则返回对应的椅子\n",
    "                return seat\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        arrivals = []\n",
    "        leavings = []\n",
    "\n",
    "        for i, (arrival, leaving) in enumerate(times):\n",
    "            arrivals.append((arrival, i))\n",
    "            leavings.append((leaving, i))\n",
    "        \n",
    "        arrivals.sort()\n",
    "        leavings.sort()\n",
    "\n",
    "        avails = []\n",
    "        mx = 0\n",
    "        i = 0\n",
    "        seats = {}\n",
    "\n",
    "        for arrival, person in arrivals:\n",
    "            while leavings[i][0] <= arrival:\n",
    "                heapq.heappush(avails, seats[leavings[i][1]])\n",
    "                i += 1\n",
    "            if avails:\n",
    "                seat = heapq.heappop(avails)\n",
    "            else:\n",
    "                seat = mx\n",
    "                mx += 1\n",
    "            if person == targetFriend:\n",
    "                break \n",
    "            seats[person] = seat \n",
    "        \n",
    "        return seat\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []   # 到达操作的时刻和对应的人\n",
    "        leaving = []   # 离开操作的时刻和对应的人\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        # 将到达与离开操作按照时间升序排序以方便模拟\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))   # 未被占据的椅子\n",
    "        seats = {}   # 每个人占据的椅子\n",
    "        # 双指针模拟\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            # 处理到达时间与之前的离开操作\n",
    "            # 将释放的椅子加入未被占据椅子中\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            # 处理到达操作\n",
    "            # 占据当前编号最小且未被占据的椅子\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                # 如果当前人为目标，则返回对应的椅子\n",
    "                return seat\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []   # 到达操作的时刻和对应的人\n",
    "        leaving = []   # 离开操作的时刻和对应的人\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        # 将到达与离开操作按照时间升序排序以方便模拟\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))   # 未被占据的椅子\n",
    "        seats = {}   # 每个人占据的椅子\n",
    "        # 双指针模拟\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            # 处理到达时间与之前的离开操作\n",
    "            # 将释放的椅子加入未被占据椅子中\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            # 处理到达操作\n",
    "            # 占据当前编号最小且未被占据的椅子\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                # 如果当前人为目标，则返回对应的椅子\n",
    "                return seat\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        times = [[times[i][0], times[i][1], i] for i in range(n)]\n",
    "        times.sort()\n",
    "        for i in range(n):\n",
    "            if(times[i][2] == targetFriend):\n",
    "                targetFriend = i \n",
    "                break\n",
    "        number = 0\n",
    "        heap1 = [] #被占\n",
    "        heap2 = [] #释放\n",
    "        for i in range(n):\n",
    "            a, l, _ = times[i]\n",
    "            while(heap1 and heap1[0][0] <= a):\n",
    "                _, num = heapq.heappop(heap1)\n",
    "                heapq.heappush(heap2, num)\n",
    "            if(len(heap2) == 0):\n",
    "                tmp = number\n",
    "                number += 1\n",
    "            else:\n",
    "                tmp = heapq.heappop(heap2)\n",
    "            heapq.heappush(heap1, [l,tmp])\n",
    "            if(i == targetFriend):\n",
    "                return tmp \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        arrivals = []\n",
    "        leavings = []\n",
    "\n",
    "        for i, (arrival, leaving) in enumerate(times):\n",
    "            arrivals.append((arrival, i))\n",
    "            leavings.append((leaving, i))\n",
    "        \n",
    "        arrivals.sort()\n",
    "        leavings.sort()\n",
    "\n",
    "        avails = []\n",
    "        mx = 0\n",
    "        i = 0\n",
    "        seats = {}\n",
    "\n",
    "        for arrival, person in arrivals:\n",
    "            while leavings[i][0] <= arrival:\n",
    "                heapq.heappush(avails, seats[leavings[i][1]])\n",
    "                i += 1\n",
    "            if avails:\n",
    "                seat = heapq.heappop(avails)\n",
    "            else:\n",
    "                seat = mx\n",
    "                mx += 1\n",
    "            if person == targetFriend:\n",
    "                break \n",
    "            seats[person] = seat \n",
    "        \n",
    "        return seat\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        times = [[times[i][0], times[i][1], i] for i in range(n)]\n",
    "        times.sort()\n",
    "        for i in range(n):\n",
    "            if(times[i][2] == targetFriend):\n",
    "                targetFriend = i \n",
    "                break\n",
    "        number = 0\n",
    "        heap1 = [] #被占\n",
    "        heap2 = [] #释放\n",
    "        for i in range(n):\n",
    "            a, l, _ = times[i]\n",
    "            while(heap1 and heap1[0][0] <= a):\n",
    "                _, num = heapq.heappop(heap1)\n",
    "                heapq.heappush(heap2, num)\n",
    "            if(len(heap2) == 0):\n",
    "                tmp = number\n",
    "                number += 1\n",
    "            else:\n",
    "                tmp = heapq.heappop(heap2)\n",
    "            heapq.heappush(heap1, [l,tmp])\n",
    "            if(i == targetFriend):\n",
    "                return tmp \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        times = [[times[i][0], times[i][1], i] for i in range(n)]\n",
    "        times.sort()\n",
    "        for i in range(n):\n",
    "            if(times[i][2] == targetFriend):\n",
    "                targetFriend = i \n",
    "                break\n",
    "        number = 0\n",
    "        heap1 = [] #被占\n",
    "        heap2 = [] #释放\n",
    "        for i in range(n):\n",
    "            a, l, _ = times[i]\n",
    "            while(heap1 and heap1[0][0] <= a):\n",
    "                _, num = heapq.heappop(heap1)\n",
    "                heapq.heappush(heap2, num)\n",
    "            if(len(heap2) == 0):\n",
    "                tmp = number\n",
    "                number += 1\n",
    "            else:\n",
    "                tmp = heapq.heappop(heap2)\n",
    "            heapq.heappush(heap1, [l,tmp])\n",
    "            if(i == targetFriend):\n",
    "                return tmp \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival = []\n",
    "        leaving = []\n",
    "        for i in range(n):\n",
    "            arrival.append((times[i][0], i))\n",
    "            leaving.append((times[i][1], i))\n",
    "        arrival.sort()\n",
    "        leaving.sort()\n",
    "        available = list(range(n))\n",
    "        seats = {}\n",
    "        j = 0\n",
    "        for time, person in arrival:\n",
    "            while j < n and leaving[j][0] <= time:\n",
    "                heappush(available, seats[leaving[j][1]])\n",
    "                j += 1\n",
    "            seat = heappop(available)\n",
    "            seats[person] = seat\n",
    "            if person == targetFriend:\n",
    "                return seat\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], friend: int) -> int:\n",
    "        final = times[friend][0]\n",
    "        arrival = {}\n",
    "        leaving = {}\n",
    "\n",
    "        for i, time in enumerate(times):\n",
    "            if time[0] <= final:\n",
    "                arrival[time[0] - 1] = i\n",
    "            if time[1] <= final:\n",
    "                try:\n",
    "                    leaving[time[1] - 1] += [i]\n",
    "                except:\n",
    "                    leaving[time[1] - 1] = [i]\n",
    "\n",
    "        chairs = [-1] * len(times)\n",
    "        availale = list(range(len(times)))\n",
    "        heapq.heapify(availale)\n",
    "\n",
    "        for i in range(final):\n",
    "            if i in leaving.keys():\n",
    "                for j in leaving[i]:\n",
    "                    heapq.heappush(availale, chairs[j])\n",
    "                    chairs[j] = -1\n",
    "            if i in arrival.keys():\n",
    "                chairs[arrival[i]] = heapq.heappop(availale)\n",
    "\n",
    "        return chairs[friend]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], friend: int) -> int:\n",
    "        arrival = sorted([(times[i][0], i) for i in range(len(times))])\n",
    "        leaving = sorted([(times[i][1], i) for i in range(len(times))])\n",
    "\n",
    "        chairs = [-1] * len(times)\n",
    "        availale = list(range(len(times)))\n",
    "        heapq.heapify(availale)\n",
    "\n",
    "        j = 0\n",
    "        for i in range(len(arrival)):\n",
    "            while j < len(leaving) and leaving[j][0] <= arrival[i][0]:\n",
    "                heapq.heappush(availale, chairs[leaving[j][1]])\n",
    "                j += 1\n",
    "            chairs[arrival[i][1]] = heapq.heappop(availale)\n",
    "            if arrival[i][1] == friend: return chairs[friend]\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "            n = len(times)\n",
    "            arr = []\n",
    "            lea = []\n",
    "            for i in range(n):\n",
    "                arr.append([times[i][0], i])\n",
    "                lea.append([times[i][1], i])\n",
    "            arr.sort()\n",
    "            lea.sort()\n",
    "            seats = {}\n",
    "            used = list(range(n))\n",
    "            j = 0\n",
    "            for time, person in arr:\n",
    "                while j < n and lea[j][0] <= time:\n",
    "                    used.append(seats[lea[j][1]])\n",
    "                    j += 1\n",
    "                used.sort()\n",
    "                seat = used.pop(0)\n",
    "                seats[person] = seat\n",
    "                if person == targetFriend:\n",
    "                    return seat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        arrival,leave = [],[]\n",
    "        for i,(a,b) in enumerate(times):\n",
    "            arrival.append((a,i))\n",
    "            leave.append((b,i))\n",
    "        arrival.sort(key=lambda x :x[0])\n",
    "        leave.sort(key=lambda x : x[0])\n",
    "\n",
    "        q = []        \n",
    "        for i in range(n):\n",
    "            heapq.heappush(q,i)\n",
    "\n",
    "        seats = defaultdict(int) \n",
    "        j = 0\n",
    "        for time,person in arrival: # 每个人 到达时间 和\n",
    "            while j<n and leave[j][0]<=time:\n",
    "                heapq.heappush(q,seats[leave[j][1]])\n",
    "                j+=1\n",
    "            cur_pos = heappop(q)\n",
    "            seats[person]=cur_pos\n",
    "            if person == targetFriend:\n",
    "                return cur_pos \n",
    "            \n",
    "        return -1\n",
    "       \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], friend: int) -> int:\n",
    "        end = times[friend][0]\n",
    "        start = end\n",
    "\n",
    "        arrival = {}\n",
    "        leaving = {}\n",
    "\n",
    "        for i, time in enumerate(times):\n",
    "            if time[0] <= end:\n",
    "                arrival[time[0] - 1] = i\n",
    "            if time[1] <= end:\n",
    "                try:\n",
    "                    leaving[time[1] - 1] += [i]\n",
    "                except:\n",
    "                    leaving[time[1] - 1] = [i]\n",
    "            start = min(start, time[0] - 1)\n",
    "\n",
    "        chairs = [-1] * len(times)\n",
    "        availale = list(range(len(times)))\n",
    "        heapq.heapify(availale)\n",
    "\n",
    "        for i in range(start, end):\n",
    "            if i in leaving.keys():\n",
    "                for j in leaving[i]:\n",
    "                    heapq.heappush(availale, chairs[j])\n",
    "                    chairs[j] = -1\n",
    "            if i in arrival.keys():\n",
    "                chairs[arrival[i]] = heapq.heappop(availale)\n",
    "\n",
    "        return chairs[friend]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        # 虽然题目说是无数张椅子，但是n-1就是峰值了\n",
    "        n = len(times)\n",
    "        times = sorted([[a, b, i] for i, (a, b) in enumerate(times)])\n",
    "        h = []\n",
    "        for i in range(n):\n",
    "            heappush(h, i)\n",
    "        \n",
    "        release = []\n",
    "        \n",
    "        for a, b, i in times:\n",
    "            while release and release[0][0] <= a:\n",
    "                _, x = heappop(release)\n",
    "                heappush(h, x)\n",
    "            v = heappop(h)\n",
    "            if i == targetFriend:\n",
    "                return v\n",
    "            heappush(release, [b, v])\n",
    "            \n",
    "           \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        n = len(times)\n",
    "        s = SortedList(list(range(n)))\n",
    "        m = {}\n",
    "        t = SortedList()\n",
    "        for i, (a, l) in enumerate(times):\n",
    "            t.add((a, 1, i))\n",
    "            t.add((l, 0, i))\n",
    "        # print(t)\n",
    "        for time, _, i in t:\n",
    "            if i == targetFriend:\n",
    "                return s[0]\n",
    "            if i not in m:        \n",
    "                m[i] = s[0]\n",
    "                s.discard(m[i])\n",
    "            else:\n",
    "                s.add(m[i])\n",
    "            # print(i, m, s)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:\n",
    "        # 按照时间戳进行模型即可，用hashmap记录哪个人做了哪个椅子，k为人id,v为椅子id,\n",
    "        # 一旦人离开，删除kv对，并在未被占据的椅子中加入该椅子编号，还要以较小的还见复杂度找到违背赵局的椅子中的较小者，堆\n",
    "        # 最多需要n把椅子\n",
    "        q=[]\n",
    "        for i,(s,e) in enumerate(times):\n",
    "            q.append((s,i,1))\n",
    "            q.append((e,i,-1))\n",
    "        q.sort(key=lambda x:(x[0],x[2]))\n",
    "        n=len(times)\n",
    "        pq=[i for i in range(n)]\n",
    "        heapify(pq)\n",
    "        hashmap={}\n",
    "        for t,i,flag in q:\n",
    "            if flag==1:\n",
    "                index=heappop(pq)\n",
    "                hashmap[i]=index\n",
    "                if i==targetFriend:\n",
    "                    return index\n",
    "            else:\n",
    "                index=hashmap.pop(i)\n",
    "                heappush(pq,index)\n",
    "        # return "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
